package heap;

import org.junit.Test;

import java.util.Random;



/*
 *@description 数组的第k个最大元素
 *@author hkfan
 *@version 1.0
 *@create 2025/5/16 14:13
 */
public class LeetCode_215 {

    @Test
    public void test(){
        System.out.println(findKthLargest(
                new int[]{3,2,3,1,2,4,5,5,6},
                4
        ));
    }



    public int findKthLargest(int[] nums, int k) {
        //1. 执行快排选择算法
        return quickSelect(nums,nums.length - k,0,nums.length-1);
    }

    /**
     * @description 使用快排思想，快速选择
     * @author hkfan
     * @throws
     * @return int
     * @time 2025/5/16 14:32
     */
    private int quickSelect(int[] nums, int k, int l, int r) {
        //1. 随机选择基准，并进行分类
        int i = updateArrays(nums,l,r);
        //2. 根据i值判断
        if(i==k){
            return nums[i];
        }else if (i>k){ //前侧
            return quickSelect(nums,k,l,i-1);
        }else{
            return quickSelect(nums,k,i+1,r);
        }
    }

    private int updateArrays(int[] nums, int l, int r) {
        int k = (int)(Math.random()*(r-l+1))+l,temp=nums[k],i=l;
        swap(nums,k,r);
        for (int j = l; j < r; j++) {
            if (nums[j]<temp){
                swap(nums,i,j);
                i++;
            }
        }
        swap(nums,i,r);
        return i;



    }

    public static int[] swap(int[] result,int a,int b){
        int temp=result[a];
        result[a]=result[b];
        result[b]=temp;
        return result;
    }


}
